A communication channel, whether it is a fiber optic channel, a co-axial channel, a wired channel, a wireless channel, or a bus connecting locations in a system over which large amounts of data are transferred, can add noise and error to information being transmitted over the channel. To correct for errors added by the communication channel, information can be sent in the form of codewords, where each codeword contains the same number of total bits and in which a number of the bits are information (message) bits and a number of bits are used for error correction. A codeword having a length of n bits includes k bits for the message length of the code and r=n−k redundant bits. The r bits are for correction and may be r parity check bits. A parity check matrix, H, contains a set of parity check equations that define the codeword according to the relation:HCT=0,
where C is the n-dimensional vector of the codeword bits. At a receiver if this relation is not satisfied, then the received codeword is not valid and must either be corrected or retransmitted.
A variety of schemes for decoding a codeword that has propagated through a communication channel exist. Some schemes may provide accuracy, and other schemes may provide fast decoding. In high speed data communication what is needed is a decoding scheme that is accurate and fast, but at the same time can be implemented without a significant amount of complexity.